package com.hyb.algorithm.data.struct.dp;

import java.util.ArrayList;
import java.util.List;

/**
 * 120. 三角形最小路径和
 * https://leetcode.cn/problems/triangle/
 * <p>
 * 示例 1：
 * <p>
 * 输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
 * 输出：11
 * 解释：如下面简图所示：
 * 2
 * 3 4
 * 6 5 7
 * 4 1 8 3
 * 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
 *
 * @author: ybhu
 * @create: 2024/01/02 08:59
 */
public class MinimumTotal {

    public static void main(String[] args) {

        List<List<Integer>> triangle = new ArrayList<>();
        triangle.add(new ArrayList<Integer>() {
            {
                add(2);
            }
        });

        triangle.add(new ArrayList<Integer>() {
            {
                add(3);
                add(4);
            }
        });


        triangle.add(new ArrayList<Integer>() {
            {
                add(6);
                add(5);
                add(7);
            }
        });

        triangle.add(new ArrayList<Integer>() {
            {
                add(4);
                add(1);
                add(8);
                add(3);
            }
        });


        int res = new MinimumTotal().minimumTotal(triangle);

        System.out.println(res);

    }


    public int minimumTotal(List<List<Integer>> triangle) {

        int n=triangle.size();
        int[][] f=new int[n][n];

        f[0][0]=triangle.get(0).get(0);

        //i代表是多少行 也就是list 的size
        for(int i=1;i<n;i++){

            //i行最左边第0列
            f[i][0]=f[i-1][0]+triangle.get(i).get(0);
            // j 代表多少列，列是 i+1
            for(int j=1;j<i;j++){
                f[i][j]=Math.min(f[i-1][j-1],f[i-1][j])+triangle.get(i).get(j);
            }

            f[i][i]=f[i-1][i-1]+triangle.get(i).get(i);
        }

        //最终的答案即为 f[n−1][0]f[n-1][0]f[n−1][0] 到 f[n−1][n−1]f[n-1][n-1]f[n−1][n−1] 中的最小值，其中 nnn 是三角形的行数。
        int res=f[n-1][0];
        for(int i=1;i<n;i++){
            res=Math.min(res,f[n-1][i]);
        }

        return res;
    }
}
